Maximum Clique Approach for Protein Binding Detection

Kati Rozman
National Institute of Chemistry, Hajdrihova 19, 1000 Ljubljana, Slovenia

Abstract:

Algorithm is adapted for finnding similarities in protein structures. Also, these algorithms are used for comparing protein structures, to provide the information about protein function and also the information about possible interactions between proteins. The principles of graph theory are adopted to investigate protein structures and predicting protein binding sites. This is done using our new maximum clique algorithm. Finding a maximum clique in an undirected graph is one of the most important NP-hard problems in discrete mathematics and theoretical computer science. Optimization problems and algorithms that can be used for solving maximum clique problem are described, and used for protein side prediction. Here is presented a few test cases for PDB protein structures.